Countless applications presently exist for automated solid modeling, the automated representation, manipulation, analysis and display of solid objects. Perhaps the primary application for solid modeling systems at present are in CAD/CAM (Computer-Aided Design and Computer-Aided Manufacture) systems. Such systems permit the efficient design and analysis of mechanical parts, the analysis of space utilization processes (for instance packaging, process planning, robotics, parts assembly, etc.), molecular modeling, and literally countless of other uses.
Solid modeling systems have also been applied to medical imaging, where an image of a portion of a human body is generated from data acquired by a CT (Computer Tomography), NMR or Ultrasound Scanner to permit a physician to study, analyze and manipulate the image. Using such systems, physicians are able to selectively view portions of the anatomy under study from various viewing angles and at different magnifications, employ an "electronic scapel" to cut out parts of the anatomy, analyze volumes and displacements to determine the size and location of anatomical structures, etc.
Another useful application of solid modeling systems is in flight simulators, which permit a pilot to train under a variety of flight conditions without the associated danger and cost of using an actual aircraft. Another application is in seismology, wherein a geologist may study and analyze images created from acoustical or electromagnetic data indicative of mineral structures of the earth's surface in order to predict the location of valuable mineral deposits, the occurrence of seismological disturbances, etc. Yet another application is in the field of artificial vision wherein templates of three-dimensional objects viewed from various angles and perspectives must be compared with observed data to permit the recognition of objects. Further applications of solid modeling systems include the generation of realistic images of physical objects or analytically-defined objects and permitting the interactive manipulation of these images for use in cinematography and video arcade games. As solid modeling systems become more efficient and less costly, numerous other applications for them will no doubt be found.
There are several different solid modeling systems presently commercially available, but all of them are limited by restrictions on the way in which the object to be imaged is represented or the speed at which the image is generated. Many available systems do not permit an object of arbitrary complexity to be represented. Others can operate on objects of essentially arbitrary complexity and configurations, but require a substantial amount of real time to generate single images (often the time to generate one image may be measured in minutes or hours) because of the extremely large number of calculations required to perform interference detection, hidden-surface removal and object manipulation on such arbitrarily complex objects.
Of course, the time it takes to generate an image is not critical in many applications. However, if a human being must interact with the image generation process (for instance, to define points of view, scaling factors, sectional views, etc.), it may be desirable to generate images in real time. For instance, video arcade games and flight simulators require a real time response in generated images when a user operates various interactive input devices. Likewise, the creative thought processes of a physician would be severely inhibited if he or she had to wait minutes or hours after specifying a view of a portion of a patient's anatomy before actually seeing the resulting image. Productivity of a CAD/CAM system decreases dramatically as the time required to generate each image increases.
Some commercially available graphics systems reduce the time required to generate images by not truly modeling the three-dimensional object to be imaged, but rather projecting only the edges (rather than the surfaces) of the object onto a display screen. The determination of what is actually solid is left to human interpretation in such imaging systems. While quite suitable for many applications, such systems (which in reality can only be used as sophisticated automated drafting systems) do not produce realistic images of solids.
Various schemes for representing solid objects to be imaged are employed by existing true solid modeling systems. Some systems define the object to be imaged through primitive instancing, wherein families of objects are defined in terms of a primitive shape type (for example, a certain kind of polyhedron) and a limited set of parameters further specifying the shape. Spatial enumeration, wherein an object is represented by the cuboid spatial three-dimensional cells which it occupies, is another method conventionally used to define a three-dimensional object. A generalized form of spatial enumeration is cell decomposition, in which the spatial cells are not necessarily cuboid or even identical. Another method conventionally used is constructive solid geometry (CSG), wherein objects are represented as collections of primitive solids such as cuboids, cylinders, etc. Tree structures are typically used to organize the primitive solids, wherein leaf nodes of the tree represent the primitives and branch nodes specify set operations performed on the primitives. Yet another method of representing a solid is by defining it as the volume swept by a two-dimensional or three-dimensional shape as it is translated along a curve. Finally, boundary representation is conventionally used to represent objects by characterizing them according to their enclosing surfaces (i.e. planes, quadric surfaces, patches, etc.).
Specific advantages and disadvantages of the various methods of object representation conventionally employed together with a classification of some existing solid modeling systems may be found in Requicha, A., and Voelcker, H., "Solid Modeling: Current Status and Research Directions," IEEE Computer Graphics and Applications, Vol. 3, No. 7, October 1983, pp. 25-37, and Requicha, A., and Voelcker, H., "Solid Modeling: A Historical Summary and Contemporary Assessment," IEEE Computer Graphics and Applications, Vol. 2, No. 2, March 1982, pp. 9-24. See also Baer, A., Eastman, C., and Henrion, M., "Geometric Modeling: A Survey," Computer-Aided Design, Vol. 11, No. 5, September 1979.
Most commercially available solid modeling systems use either constructive solid geometry or boundary representation (or a combination of the two) as the primary scheme to represent the object. For example, the TIPS, the PADL, and the SynthaVision systems use a constructive solid geometry representation scheme; the Build, CADD, Design, Solidesign and Romulus systems employ the boundary representation scheme; the EUKLID and GMSolid systems use a combination of these two schemes. Some systems permit alternate representations, such as alternate data input schemes wherein an object may be defined by the swept volume representation. The TIPS system can sort the primitives into a spatial enumeration array to facilitate interference analysis.
New methods are needed to solve or at least reduce a number of problems which have plagued solid modeling systems developed in the past. Many existing systems seriously restrict the objects which can be imaged because of the constraints imposed by the representation scheme used. Serious limitations are imposed when the object must be defined by a limited number of mathematically well-defined surface or solid primitives. Many schemes cause extraneous surfaces not corresponding to true surfaces in the three-dimensional object to be included in the generated images due to imprecision in the object representation.
An important drawback of present solid modeling systems where real time image generation is desired is the often huge amount of data required to represent an object of arbitrary complexity, and the efficiency of the operations which must be performed on this data to generate an image. The computational complexity and memory requirements of algorithms used to generate the image should not grow at a rate faster than linear with the number and complexity of objects to be imaged. Most present systems which can represent objects of arbitrary complexity do not satisfy these requirements.
Finally, most existing solid modeling systems were designed using limited hardware and storage resource design constraints. Because the amount of hardware is often traded off with the speed performance of the system, existing solid modeling systems generally have poor speed performance as a result. With the advent of inexpensive solid state memory and hardware (brought about by the advent of VLSI technology), larger amounts of hardware can now be used at relatively little cost to achieve faster processing time than could be realized previously.
One of the keys to the efficient generation of images of solids is to limit algorithms to a linear growth rate. One method which may be used to limit growth rate in image generation is the hierarchical subdivision of the display surface into progressively smaller areas. Such a scheme is disclosed in Warnock (U.S. Pat. No. 3,602,702, issued Aug. 31, 1971), which discloses a method and system for electronically generating and displaying shaded two-dimensional perspective images of three-dimensional objects. Warnock discloses the representation of an object to be displayed by planar polygonal surface primitives resulting when the object is projected onto a view plane. A square view plane is subdivided into a number of subsquares, each of which may be further subdivided if necessary. The surface primitive is tested with respect to the various subsquares of the view plane to determine whether the subsquare is enclosed by the surface primitive, intersects but does not enclose the surface primitive, or is completely disjoint with the surface primitive. These tests are performed by comparing the coordinates of each of the line segments of the surface primitive with the coordinates of the subsquare of the view plane under test.
A subsquare which is entirely enclosed by a surface primitive may be shaded on a display screen. Subsquares which intersect but are not enclosed by the surface primitive are further subdivided until a level of resolution along the edge of the surface primitive is reached. Of course, during the subdivision process, new subsquares which are found to be enclosed by the surface primitive are appropriately shaded.
The use of two-dimensional hierarchical tree structures called "quadtrees" in the field of image processing to represent a hierarchically-subdivided display surface was proposed in Hunter, G. M. and Steiglitz, K., "Operations on Images Using Quad Trees," IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. PAMI-1, No. 2, April 1979. Rosenfeld, A., "Quadtrees and Pyramids for Pattern Recognition and Image Processing," Proceedings of the 5th International Conference on Pattern Recognition, December 1980, discusses the use of quadtrees in pattern recognition and image processing. Samet, H., and Rosenfeld, A., "Quadtree Representation of Binary Images," Proceedings of the 5th International Conference on Pattern Recognition, December 1980, presents an overview of quadtrees, while Samet, H., "Neighbor Finding Techniques for Images Represented by Quadtrees," Computer Graphics and Image Processing, Vol. 18, 1982, 37-57 discusses techniques for finding neighbors for images represented by quadtrees.
The use of an 8-ary hierarchical tree to represent three-dimensional objects has been suggested in Hunter, G. M., "Efficient Computation and Data Structures for Graphics," PhD dissertation, Electrical Engineering and Computer Science Department, Princeton University, June 1978 as an extension of quadtrees. This concept was discussed in Jackins, C. L., and Tanimoto, S. L., "Oct-Trees and Their Use in Representing Three-Dimensional Objects," Technical Report 74-07-06, Department of Computer Science, University of Washington, Seattle, July 1979; Jackins, C. L., and Tanimoto, S. L., "Oct-Trees and Their Use in Representing Three-Dimensional Objects," Computer Graphics and Image Processing, December 1980; Srihari, S. N., "Representation of Three-Dimensional Digital Images," Technical Report No. 162, Dept. of Computer Science, State University of New York at Buffalo, July 1980; Srihari, S. N., "Hierarchical Representations for Serial Section Images," Proceedings of the 5th International Conference on Pattern Recognition, December 1980; Meagher, D., "Octree Encoding: A New Technique for the Representation, Manipulation and Display of Arbitrary 3-D Objects by Computer," Technical Report IPL-TR-80-111, Image Processing Laboratory, Rensselaer Polytechnic Institute, October 1980. Later papers discussing octree encoding include Doctor, L. J. and Torborg, J. G., "Display Techniques for Octree-Encoded Objects," IEEE Computer Graphics and Applications, Vol. 1, No. 3, July 1981; Doctor, L., "Solid Modeling Algorithms Utilizing Octree Encoding," Center for Interactive Computer Graphics, Rensselaer Polytechnic Institute, December 1980; Iftikhar, A., "Linear Geometric Transformations on Octrees," M. S. thesis, Electrical, Computer and Systems Engineering Department, Rensselaer Polytechnic Institute, May 1981; and Yau, M. M., and Srihari, S. N., "Recursive Generation of Hierarchical Data Structures for Multidimensional Digital Images," Technical Report No. 170, Dept. of Computer Science, State University of New York at Buffalo, January 1981.
Additionally, the present inventor has published several papers discussing octree encoding. After publishing the paper in October of 1980 which discloses an octree encoding scheme, the present inventor presented additional results in Meagher, D., "Geometric Modeling Using Octree Encoding," Computer Graphics and Image Processing, 19, June 1982. A display algorithm was discussed in Meagher, D., "High Speed Display of 3-D Medical Images Using Octree Encoding," IPL-TR-021, Image Processing Laboratory, Rensselaer Polytechnic Institute, September 1981, and an updated version of the display algorithm was presented in Meagher, D., "Efficient Synthetic Image Generation of Arbitrary 3-D Objects," Proc. IEEE Computer Society Conference on Pattern Recognition and Image Processing, June 1982. The development of efficient object generation algorithms was documented in Meagher, D., "Octree Generation, Analysis and Manipulation," IPL-TR-027, Image Processing Laboratory, Rensselaer Polytechnic Institute, April 1982. Finally, a summarization of the octree encoding scheme and algorithms used in conjunction with that scheme for efficient solid modeling was disclosed in Meagher, D., "The Octree Encoding Method for Efficient Solid Modeling," IPL-TR-032, Image Processing Laboratory, Rensselaer Polytechnic Institute, August, 1982. All of the above cited documents authored by Donald J. R. Meagher are hereby explicitly incorporated herein by reference.